Congruencia modulo n

En Z:aRbab(n)nab\text{En }\Z: \quad aRb \Leftrightarrow a\equiv b(n)\Leftrightarrow n\vert a-b

x={yZ/y=nk+xcon kZ}\overline{x} =\{y\in Z/y=nk+x\quad \text{con }k\in \Z \}

Zn={0,1,2,,n1}\Z_n=\{\overline{0},\overline{1},\overline{2},\ldots,\overline{n-1}\}

x,yZ:Si xa(n)yb(n)x+ya+b(n)\forall x,y\in \Z : \text{Si } x\in\overline{a}(n)\land y\in\overline{b}(n) \rArr x+y \in \overline{a+b}(n)

x,yZ:Si xa(n)yb(n)xyab(n)\forall x,y\in \Z : \text{Si } x\in\overline{a}(n)\land y\in\overline{b}(n) \rArr x\cdot y \in \overline{a\cdot b}(n)

Funcion de Euler

ϕ(n)={xN/xnmcd(x,n)=1}\phi (n) = \lvert \{x\in\N / x\leq n\land \text{mcd}(x,n)=1 \} \rvert

Osea me devuelve cuantos numeros coprimos hay hasta el numero nn

  1. Si pp es un numero primo, entonces: ϕ(p)=p1\phi(p)=p-1
  2. Si n es un numero natural y p es numero primo: ϕ(pn)=pn(11p)ϕ(pn)=pn1(p1)\phi(p^n) = p^n\cdot \left(1-\frac{1}{p}\right) \quad \phi(p^n) =p^{n-1}(p-1)
  3. Si n,mN y mcd(n,m)=1:ϕ(nm)=ϕ(n)ϕ(m)n,m\in\N \text{ y mcd}(n,m)=1:\phi(n\cdot m)=\phi(n)\cdot \phi(m)
  4. ϕ(n)=n(11p1)(11p2)(11pr)\phi(n)= n\cdot \left(1-\frac{1}{p_1}\right)\cdot \left(1-\frac{1}{p_2}\right)\cdot\cdots\cdot\cdot \left(1-\frac{1}{p_r}\right)

Teorema de Fermat

Se usa para las ecuaciones de congruencia o para calcular las divisiones de numeros demasiado grandes

Si p es primomcd(a,p)=1ap11(p)\text{Si }p\text{ es primo} \land \text{mcd}(a,p)= 1\rArr a^{p-1}\equiv 1(p)

Este teorema se usa para ir simplificando los exponentes para verificar si el resto de una division cae en una clase

Teorema de Euler-Fermat

Si mcd (a,n)=1aϕ(n)1(n)\text{Si mcd } (a,n)=1 \rArr a^{\phi(n)}\equiv 1(n)

Ecuaciones Lineales de Congruencia

axb(n)a\cdot x\equiv b(n)

Sea axb(n).Si mcd (a,n)=1 entonces hay solucion.\text{Sea } a\cdot x\equiv b(n).\qquad \text{Si mcd }(a,n)=1 \text{ entonces hay solucion.}

x=aϕ(n)1bx=a^{\phi(n)-1}\cdot b

axb(n) tiene solucion mcd(a,n)b y la cantidad de soluciones es mcd(a,n)a\cdot x \equiv b(n) {\small\text{ tiene solucion }} \Leftrightarrow \text{mcd}(a,n)\vert b\quad {\small\text{ y la cantidad de soluciones es }} \text{mcd} (a,n)

Esto sirve tambien para simplificar las ecuaciones, se puede dividir termino a termino por la cantidad de soluciones, luego resolver la ecuacion, y finalmente al resultado de la eq simplificada se le suma el modulo simplificado la cantidad de soluciones que hallamos obtenido.

Si:acbc(n)mcd(c,n)=1Entonces ab(n)\text{Si}: a\cdot c\equiv b\cdot c(n)\land \text{mcd}(c,n)=1 \quad \text{Entonces }a\equiv b(n)